package com.itheima.leetcode;

import java.util.Arrays;

/**
 * 最小覆盖子串 - 双指针
 */
public class MinWindowLeetcode76 {

    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
    }

    /**
     * 1. 统计目标串需要各种字符个数，统计原始串 i~j 各种字符个数<br>
     * 2. 如果原始串 i~j 范围内不满足条件，j++ 扩大范围，直到满足条件 j 停下来<br>
     * 3. 一旦满足条件 i++ 缩小范围，直到再次不满足条件 ...<br>
     * 4. 重复 2.3，两步直至 j 到达原始串末尾<br>
     *
     * @param s
     * @param t
     * @return
     */
    public static String minWindow(String s, String t) {
        char[] target = t.toCharArray();
        int[] targetCount = new int[128]; // 阿斯克码一共有128个字符编码。‌
        for (char ch : target) {
            targetCount[ch]++;
        }
        System.out.println(Arrays.toString(targetCount));

        int passTotal = 0; // 条件总数
        for (int count : targetCount) {
            if (0 < count) {
                passTotal++;
            }
        }
        System.out.println("条件总数：" + passTotal);
        int passed = 0; // 已通过的条件数

        char[] source = s.toCharArray();
        int[] sourceCount = new int[128]; // 原始串 i~j 范围内字符各出现次数
        int i = 0;
        int j = 0;
        Result res = null;
        while (j < source.length) {
            // 扩大 j 范围，更新范围内字符计数 和 通过条件数
            char right = source[j];
            sourceCount[right]++;
            if (sourceCount[right] == targetCount[right]) { // 如果超过 targetCount[right] 仍会累加，相同字母 passed 只累加一次
                passed++;
            }
            System.out.println("处理的字符：" + right + "通过数：" + passed);
            System.out.println(Arrays.toString(sourceCount));
            System.out.println("-----------------------------------------");
            // 若已满足所有条件，缩小 i 范围，更新范围内字符计数 和 通过条件数
            while (passTotal == passed && i <= j) {
                if (null == res) {
                    res = new Result(i, j);
                } else {
                    if (j - i < res.j - res.i) {
                        res = new Result(i, j);
                    }
                }
                char left = source[i];
                sourceCount[left]--;
                if (sourceCount[left] < targetCount[left]) {
                    passed--;
                }
                i++;
            }
            j++;
        }
        System.out.println(res.i + "" + res.j);
        return null == res ? "" : new String(source, res.i, res.j - res.i + 1);
    }

    static class Result {
        int i;
        int j;

        public Result(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }

}
